package com.atguigu.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 图
 * 邻接矩阵(二维数组)
 * 邻接表(链表)
 * 遍历:
 * 深度优先算法(DFS)
 * 步骤：
 * 1.访问初始节点v并标记为已访问
 * 2.查找节点v的第一个邻接节点w
 * 3.如果w存在，则执行4，如果不存在则回到第一步，将从v的下一个节点继续
 * 4.如果节点w未被访问，对w进行深度优先遍历递归（即:吧w当成另一个v，然后执行步骤1.2.3）
 * 5.如果节点w已经被访问,则查找v的w邻接结点的下一个邻接结点，然后转到步骤3
 * 广度优先算法(BFS)
 * 步骤：
 * 1.访问初始节点v并标记节点v已访问
 * 2.节点v进入对列
 * 3.当对列非空时继续执行，否则结束
 * 4.出队列，取得队列头节点u
 * 5.查找节点u的第一个邻接节点w
 * 6.若节点u的邻接节点w不存在，转到步骤3,否者循环执行下面三个步骤
 * 6.1 若节点w未被访问，则访问结点w并标记未已访问
 * 6.2 节点w入对列
 * 6.3查找节点u的继w邻接节点后的下一个邻接节点w,转到步骤6
 *
 * @author dataexa
 * @Date 2024/1/22
 */
public class GraphTest {


    public static void main(String[] args) {
        int n = 5;
        String[] vertexValue = {"A", "B", "C", "D", "E"};
//        Graph graph = new Graph(n);
        GraphDFS graph = new GraphDFS(n);
        for (String s : vertexValue) {
            graph.insertVertex(s);
        }
        // 添加边
        // A-B,A-C,B-C,B-D,D-E
        graph.insertEdge(0, 1, 1);
        graph.insertEdge(0, 2, 1);
        graph.insertEdge(1, 2, 1);
        graph.insertEdge(1, 3, 1);
        graph.insertEdge(3, 4, 1);
        graph.showGraph();
        graph.dfs();

    }

    public void dfs(List<String> vertexList, int[][] edges) {

    }

}


// 深度优先算法
class GraphDFS {
    private List<String> vertexList; // 顶点
    private int[][] edges; //边得邻接矩阵
    private int numOfEdges; // 边得数目
    private boolean[] isVisited;  // 记录莫一个节点是否被访问

    // 得到第一个邻接节点的下标 
    public int getFirstNeighbor(int index) {
        for (int i = 0; i < vertexList.size(); i++) {
            if (edges[index][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    // 根据前一个邻接节点的下标获取下一个邻接节点下标
    public int getNextNeighbor(int v1, int v2) {
        for (int i = v2 + 1; i < vertexList.size(); i++) {
            if (edges[v1][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    // 对一个节点进行DFS深度优先算法
    public void dfs(boolean[] isVisited, int i) {
        // 访问初始节点i
        System.out.print(getVertexByIndex(i) + "->");
        // 将该节点设置为已访问
        isVisited[i] = true;
        // 查找节点的第一个邻接节点w
        int w = getFirstNeighbor(i);
        while (w != -1) {
            // 如果节点w未被访问
            if (!isVisited[w]) {
                dfs(isVisited, w);
            }
            // 如果w结点已经被访问了,i是当前节点的小标，w是找到的邻接节点的小标
            w = getNextNeighbor(i, w);
        }
    }

    // 对dfs进行一个重载，遍历我们所有的节点并进行dfs
    public void dfs() {
        //遍历所有节点
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {
                dfs(isVisited, i);
            }
        }
    }


    // 对一个节点进行广度优先遍历的方法
    public void bfs(boolean[] isVisited, int i) {
        int u; //表示队列的头节点的下标
        int w; // 邻接节点w
        //节点访问队列，记录节点的访问顺序
        LinkedList<Object> queue = new LinkedList<>();
        System.out.print(getVertexByIndex(i) + "->");
        // 标记为已访问
        isVisited[i] = true;
        //将节点加入对列
        queue.addLast(i);

        while (!queue.isEmpty()) {
            // 取出队列的头节点
            u = (Integer) queue.removeFirst();
            // 得到第一个邻接节点的下标
            w = getFirstNeighbor(u);
            while (w != -1) {
                if (!isVisited[w]) {
                    System.out.print(getVertexByIndex(w) + "->");
                    isVisited[w] = true;
                    queue.addLast(w);
                }
                w = getNextNeighbor(u, w); // 体现广度优先
            }
        }
    }

    // 构造器
    public GraphDFS(int n) {
        edges = new int[n][n];
        vertexList = new ArrayList<>(n);
        this.numOfEdges = 0;
        isVisited = new boolean[n];
    }

    // 常用的方法

    // 返回节点得个数
    public int getNumOfVertex() {
        return vertexList.size();
    }

    // 返回边得个数
    public int getNumOfEdges() {
        return numOfEdges;
    }

    // 获取指定下标的顶点
    public String getVertexByIndex(int index) {
        return vertexList.get(index);
    }

    // 返回v1合v2的权值
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    // 显示图对应矩阵
    public void showGraph() {
        for (int[] edge : edges) {
            System.err.println(Arrays.toString(edge));
        }
    }

    // 插入顶点
    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    /**
     * 插入边
     *
     * @param v1     表示点得下标，表示第几个点得下标
     * @param v2     表示第二个顶点得下标
     * @param weight 表示权值
     */
    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }
}

class Graph {
    private List<String> vertexList; // 顶点
    private int[][] edges; //边得邻接矩阵
    private int numOfEdges; // 边得数目

    // 构造器
    public Graph(int n) {
        edges = new int[n][n];
        vertexList = new ArrayList<>(n);
        this.numOfEdges = 0;
    }

    // 常用的方法

    // 返回节点得个数
    public int getNumOfVertex() {
        return vertexList.size();
    }

    // 返回边得个数
    public int getNumOfEdges() {
        return numOfEdges;
    }

    // 获取指定下标的顶点
    public String getVertexByIndex(int index) {
        return vertexList.get(index);
    }

    // 返回v1合v2的权值
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    // 显示图对应矩阵
    public void showGraph() {
        for (int[] edge : edges) {
            System.err.println(Arrays.toString(edge));
        }
    }

    // 插入顶点
    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    /**
     * 插入边
     *
     * @param v1     表示点得下标，表示第几个点得下标
     * @param v2     表示第二个顶点得下标
     * @param weight 表示权值
     */
    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }
}